package com.xj.algorithm.leetcode;

import java.util.*;

/**
 * 二叉搜索树中的众数
 */
public class L501_二叉搜索树中的众数 {

    /**
     * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
     * <p>
     * 假定 BST 有如下定义：
     * <p>
     * 结点左子树中所含结点的值小于等于当前结点的值
     * 结点右子树中所含结点的值大于等于当前结点的值
     * 左子树和右子树都是二叉搜索树
     * 例如：
     * 给定 BST [1,null,2,2],
     * <p>
     * 1
     * \
     * 2
     * /
     * 2
     * 返回[2].
     * <p>
     * 提示：如果众数超过1个，不需考虑输出顺序
     * <p>
     * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(2);
        int[] res = findMode(root);
        for (int v : res) {
            System.out.println(v + ",");
        }

        int[] res2 = findModeGood(root);
        for (int v : res2) {
            System.out.println(v + ",");
        }
    }

    //自己的解法：先左根右的遍历，将数组存储到数组中，然后map统计所有众数
    public static int[] findMode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);

        if(list.size()==0){
            return new int[]{};
        }

        int last = list.get(0);
        int count=1;
        int max=Integer.MIN_VALUE;
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) != last) {
                map.put(last,count);
                last=list.get(i);
                count=1;
            }else{
                count++;
            }
            max=max<count?count:max;
        }
        map.put(last,count);
        max=max<count?count:max;

        //遍历map,找到最值
        List<Integer> res=new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue()==max){
                res.add(entry.getKey());
            }
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }

    public static void inorder(TreeNode root, List list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }


    //精彩解法：直接在中序遍历的时候就进行众数比较，有几个全局变量
    static int maxTimes = 0;
    static int thisTimes = 0;
    static List<Integer> res = new LinkedList<Integer>();
    static TreeNode pre = null;

    public static int[] findModeGood(TreeNode root) {
        inOrderGood(root);
        int length = res.size();
        int[] rr = new int[length];
        for(int i = 0; i < length; i++) {
            rr[i] = res.get(i);
        }
        return rr;
    }

    public static void inOrderGood(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrderGood(root.left);
        if(pre != null && pre.val == root.val) {
            thisTimes++;
        } else {
            thisTimes = 1;
        }
        if(thisTimes == maxTimes) {
            res.add(root.val);
        } else if(thisTimes > maxTimes) {
            maxTimes = thisTimes;
            res.clear();
            res.add(root.val);
        }
        pre = root;
        inOrderGood(root.right);
    }

}
